package alo.p4.work;


import java.util.Stack;

//getMinimum（）的操作的时间复杂度为O（1）
//getMinimum（）-->获取最小值的函数
//建立另一个栈，空间复杂度为O（n）
public class AdvancedStack {
    private Stack elementStack =new Stack();
    private Stack minStack =new Stack();
    public void push(int data){
        elementStack.push(data);
        //当新入栈的元素的值比最小的小，那么把小的入栈
        //否则，把最小的在入栈
        //即两个栈的元素个数是一样的
        if (minStack.isEmpty()||(Integer)minStack.peek()>=(Integer) data){
            minStack.push(data);
        }else {
            minStack.push(minStack.peek());
        }
    }
    public Integer pop(){
        if (elementStack.isEmpty()) return null;
        minStack.pop();
        return (Integer) elementStack.pop();
    }
    public int getMinimum(){
        return (int) minStack.peek();
    }
    public int top(){
        return (int) elementStack.peek();
    }
    public boolean isEmpty(){
        return elementStack.isEmpty();
    }
    //这种情况不重复入栈最小值，比第一种情况的空间的使用更少
    class AdvancedStack2{
        private Stack elementStack =new Stack();
        private Stack minStack =new Stack();
        public void push(int data){
            elementStack.push(data);
            //当新入栈的元素的值比最小的小，那么把小的入栈
            if (minStack.isEmpty()||(Integer)minStack.peek()>=(Integer) data){
                minStack.push(data);
            }
        }
        public Integer pop(){
            if (elementStack.isEmpty()) return null;
            Integer minTop= (Integer) minStack.peek();
            Integer elementTop= (Integer) elementStack.peek();
            //当出栈的数据是最小的时候，把minStack的最小值也出栈
            if (minTop==elementTop) minStack.pop();
            return (Integer) elementStack.pop();
        }
        public int getMinimum(){
            return (int) minStack.peek();
        }
        public int top(){
            return (int) elementStack.peek();
        }
        public boolean isEmpty(){
            return elementStack.isEmpty();
        }

    }
}
